#define _CRT_SECURE_NO_WARNINGS	

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A)
    {
        // write code here
        ListNode* slow, * fast;
        slow = fast = A;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = (fast->next)->next;
        }
        ListNode* tmp, * newhead = NULL;
        while (slow)
        {
            tmp = slow->next;
            slow->next = newhead;
            newhead = slow;
            slow = tmp;
        }
        ListNode* head = A;
        while (head && newhead)
        {
            if (head->val != newhead->val)
                return false;
            head = head->next;
            newhead = newhead->next;
        }
        return true;
    }
};